package com.shapo.util;

import java.util.*;
import java.io.*;

public class SplayTree< E extends Number > {
	private ArrayList<Integer> leftSon, rightSon, par;
	private ArrayList<E> key;
	private ArrayList<Integer> hash;
	private Stack<Integer> avail;
	int root, factor;
	
	public SplayTree() {
		this(10);
	}
	
	public SplayTree(int factor_size) {
		root = 0;
		factor = factor_size;
		init();
	}
	
	public boolean empty() {
		return (root == 0);
	}
	
	public boolean find(E x) {
		return (!empty() && key.get(accessItem(x)).hashCode() == x.hashCode());
	}
	
	private int g(int x) {
		return par.get(par.get(x));
	}
	
	private void init() {
		leftSon = new ArrayList<Integer>();
		rightSon = new ArrayList<Integer>();
		par = new ArrayList<Integer>();
		key = new ArrayList<>();
		hash = new ArrayList<Integer>();
		leftSon.add(0);
		rightSon.add(0);
		key.add((E) new Object());
		par.add(0);
		hash.add(0);
	}
	
	private void rotate(int y, int dir) {
		// if dir == 0 then rotateLeft
		// if dir == 1 then rotateRight
		int x = ((dir != 0) ? leftSon.get(y) : rightSon.get(y)),
			z = par.get(y);
		if (z != 0) {
			if (leftSon.get(z) == y)
				leftSon.set(z, x);
			else
				rightSon.set(z, x);
		}
		if (dir == 0) {
			rightSon.set(y, leftSon.get(x));
			leftSon.set(x, y);
			if (rightSon.get(y) != 0)
				par.set(rightSon.get(y), y);
		} else {
			leftSon.set(y, rightSon.get(x));
			rightSon.set(x, y);
			if (leftSon.get(y) != 0)
				par.set(leftSon.get(y), y);
		}
		par.set(x, z);
		par.set(y, x);
	}
	
	private int splay(int x) {
		while (par.get(x) != 0) {
			if (x == leftSon.get(par.get(x))) {
				if (g(x) == 0)
					rotate(par.get(x), 1);
				else {
					if (par.get(x) == leftSon.get(g(x))) {
						rotate(g(x), 1);
						rotate(par.get(x), 1);
					} else { // par[x] == rightSon[g(x)]
						rotate(par.get(x), 1);
						rotate(par.get(x), 0);
					}
				}
			} else { // x == rightSon[par[x]]
				if (g(x) == 0)
					rotate(par.get(x), 0);
				else {
					if (par.get(x) == rightSon.get(g(x))) {
						rotate(g(x), 0);
						rotate(par.get(x), 0);
					} else { // par[x] == leftSon[g(x)]
						rotate(par.get(x), 0);
						rotate(par.get(x), 1);
					}
				}
			}
		}
		return (root = x);
	}
	
	private int accessItem(E i) {
		if (root == 0)
			return root;
		int last = root;
		int iHash = i.hashCode();
		while (hash.get(last) != iHash) {
			if (hash.get(last) > iHash) {
				if (leftSon.get(last) != 0)
					last = leftSon.get(last);
				else
					break;
			} else {
				if (rightSon.get(last) != 0)
					last = rightSon.get(last);
				else
					break;
			}
		}
		return splay(last);
	}
	
	private int join(int t1, int t2) {
		if (t1 == 0)
			return t2;
		int last = t1;
		while (rightSon.get(last) != 0) 
			last = rightSon.get(last);
		splay(last);
		if (t2 != 0)
			par.set(t2, last);
		rightSon.set(last, t2);
		return last;
	}
	
	public int insertItem(E i) {
		int last = root, prev = root;
		int iHash = i.hashCode();
		while (last != 0 && hash.get(last) != iHash) {
			prev = last;
			last = ((hash.get(last) < iHash) ? rightSon.get(last) : leftSon.get(last));
		}
		if (last == 0) {
			if (avail.empty()) {
				int size = key.size() - 1, p = size;
				size = (size != 0) ? ((size + 1) >> 1) : factor;
				for (int it = 0; it < size; ++it) {
					init();
					avail.push(++p);
				}
			}
			last = avail.peek();
			avail.pop();
			par.set(last, prev);
			leftSon.set(last, 0);
			rightSon.set(last, 0);
			//key.set(last, ); //FIXME
			hash.set(last, iHash);
			if (hash.get(prev) < iHash)
				rightSon.set(prev, last);
			else
				leftSon.set(prev, last);
		}
		return splay(last);
	}
	
	public int deleteItem(E i) {
		int newRoot = accessItem(i),          
			iHash = i.hashCode();
		if (hash.get(newRoot) == iHash) {
			avail.push(newRoot);
			key.set(newRoot, null);
			par.set(leftSon.get(newRoot), 0);
			par.set(rightSon.get(newRoot), 0);
			return (root = join(leftSon.get(newRoot), rightSon.get(newRoot)));
		}
		return (root = newRoot);
	}
}
